Cumulative product from left to right

Just take the cumulative product from the left and the cumulative product from the right and multiply them together with one gap.

If we do it simply, O(N^2) becomes O(N).

Simple solution for N=3000 takes 3 seconds, but this method takes 2 milliseconds.

code:python

def one_out_product_fast(xs):

N = len(xs)

prod = 1

for i in range(N):

prod %= MOD

prod = 1

for i in range(N - 1, -1, -1):

prod %= MOD

return ret

def bluteforce(xs):

N = len(xs)

for i in range(N):

for j in range(N):

if i == j:

continue

return ret

code::

N=3000

%timeit one_out_product_fast(xs)

2.14 ms ± 55 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit bluteforce(xs)

2.98 s ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

---